package 普通数组.合并区间;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
/**
 * 题目描述
 * 以数组 intervals 表示若干个区间的集合，
 * 其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，
 * 并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
 * 输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
 * 输出：[[1,6],[8,10],[15,18]]
 * 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
 * 力扣链接：https://leetcode-cn.com/problems/merge-intervals/
 * 力扣题：56
 * */
/**
 * 题目思路
 * 如果ad能够合并，a的左端点小于等于b的右端点，则a和b能够合并
 * */

class Solution {
    public int[][] merge(int[][] intervals) {
        // 如果区间为空，直接返回空数组
        if(intervals.length == 0){
            return new int[0][0];
        }
        // 按左端点大小排序
        Arrays.sort(intervals,new Comparator<int[]>(){
            @Override
            public int compare(int[] o1,int[] o2){
                return o1[0] - o2[0];
            }
        });
        List<int[]> ans = new ArrayList<>();
        // 合并区间
        for(int i = 0;i < intervals.length;i++){
            // 当前区间的左，右端点
            int lef = intervals[i][0],rig = intervals[i][1];
            // 如果当前的区间的左端点小于等于上一个区间的右端点，合并区间
            while((i + 1 < intervals.length) && intervals[i + 1][0] <= rig){
                rig = Math.max(rig,intervals[i+1][1]); // 合并区间
                i++;
            }
            // 加入答案
            ans.add(new int[]{lef,rig});
        }
        // 以数组形式返回答案
        return ans.toArray(new int[ans.size()][0]);
    }
}